home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 001-025 / disk_006 / sort / sorts.c < prev   
C/C++ Source or Header  |  1992-05-06  |  13KB  |  668 lines
  1. /*
  2.  * Sort utility subroutines.
  3.  */
  4.  
  5. #ifdef    DOCUMENTATION
  6.  
  7. title    sorts    Sort Utility Subroutines
  8. index        Sort Utility Subroutines
  9.  
  10. synopsis
  11.     .nf
  12.         sorta(record)
  13.         char        *record;
  14.     .s
  15.         sorto(buffer)
  16.         char        **buffer;
  17.     .f
  18.  
  19. description
  20.  
  21.     Sorta() and sorto() comprise a general-purpose C-callable
  22.     sort utility.  There are no restrictions on file or item
  23.     size.  The routines are used as follows:
  24.     .lm +8
  25.     .s.i -4;sorta(record)
  26.     .s
  27.     Add the named record to the data to be sorted.
  28.     After adding the last record, execute "sorta(NULL)"
  29.     to terminate the data.
  30.     .s.i -4;sorto(buffer)
  31.     .s
  32.     Sort output: move the next (sorted) record into the buffer.
  33.     Return "buffer" or NULL when all records have been returned.
  34.     .s.lm -8
  35.     The routines are meant to be used in the following manner:
  36.     .s.nf
  37.         while (next_datum()) {
  38.             sorta(datum);
  39.         }
  40.         sorta(NULL);
  41.         while (sorto(buffer)) {
  42.             process(buffer);
  43.         }
  44.     .s.f
  45.     After sorto() returns NULL, sorta() may be called to start a new
  46.     sort sequence.
  47.     .s
  48.     Data is normally sorted in ascending Ascii order, using the
  49.     entire record as the key.  If this is not satisfactory, the
  50.     following global symbols may be used to modify the sort:
  51.     .lm +8
  52.     .s.i -4;extern int sort__l;
  53.     .s
  54.     This value defines the maximum record length.  It may be
  55.     changed before calling sorta() for the first
  56.     time.
  57.     .s.i -4;extern int (*sort__c)();
  58.     .s
  59.     This defines the comparison function which, by default, is strcmp().
  60.     To call a user-provided function, the main program should contain:
  61.     .s.nf
  62.         extern int (*sort_c)();
  63.         ...
  64.         main()
  65.         {
  66.             extern int    myfun();
  67.     
  68.             (*sort_c)() = _&myfun;
  69.             ...
  70.         }
  71.         ...
  72.         int myfun(record1, record2)
  73.         char    *record1, *record2;
  74.         /*
  75.          * Compare records, returning
  76.          *  -1    record1  < record2
  77.          *   0    record1 == record2
  78.          *  +1    record1  > record2
  79.          */
  80.         {
  81.             ...
  82.         }
  83.     .f
  84.     .s.i -4;extern int sort__r;
  85.     .s
  86.     This flag reverses the sense of the sort.  Thus, to sort in
  87.     reverse alphanumeric order, the main program should contain:
  88.     .s.nf
  89.         extern int sort_r;
  90.         ...
  91.         main()
  92.         {
  93.             ...
  94.             sort_r = 1;
  95.         }
  96.     .f
  97.     .s.i -4;extern char *sort__f;
  98.     .s
  99.     This names the sort work file and may be changed if, for example,
  100.     the file should be written to a private disk.  It is used
  101.     as follows:
  102.     .s.nf
  103.         extern char *sort_f;
  104.         ...
  105.         main()
  106.         {
  107.             ...
  108.             sort_f = "myfile.tmp";
  109.         }
  110.     .f
  111.     .lm -8
  112.  
  113. diagnostics
  114.  
  115.     .lm +8
  116.     .s.i -8;SORTS-E-cannot create temp. file "filename"
  117.     .s
  118.     The required file cannot be created in the current directory.
  119.     .s.i -8;SORTS-E-out of main memory.
  120.     .s
  121.     The program ran out of main memory.  Sorts may be optionally
  122.     compiled to dump internal tables (run tables) on this error.
  123.     .s.i -8;SORTS-E-Error writing temp. file
  124.     .s
  125.     An occurred when writing the temp. file.  It is probably
  126.     "out of space on the disk".
  127.     .s.i -8;SORTS-F-Can't reopen temp. file
  128.     .s.i -8;SORTS-F-Empty run
  129.     .s.i -8;SORTS-F-Unexpected eof
  130.     .s.lm -8
  131.     All error are fatal.  "-E" errors are probably correctable by the
  132.     user.  "-F" errors are serious problems.  If the user program
  133.     defined its own comparison function, that should be checked
  134.     for consistancy.
  135.  
  136. author
  137.  
  138.     David Conroy, Martin Minow
  139.     .s
  140.     Revised by Bob Denny and Tim Coad
  141.  
  142. bugs
  143.  
  144. #endif
  145.  
  146. #include <stdio.h>
  147.  
  148. #define    RUNSIZE        512
  149. #define    STACKSIZE    10        /* Log2(RUNSIZE) + 1        */
  150. #define    TEMP        "sort.tmp"
  151.  
  152. typedef struct    run {
  153.     struct    run *r_rp;
  154.     long    r_seek;
  155.     int    r_size;
  156. } RUN;
  157.  
  158. typedef struct    heap {
  159.     struct    run *h_rp;
  160.     char    *h_lp;
  161. } HEAP;
  162.  
  163. typedef struct    stack {
  164.     int    rght;
  165.     int    lft;
  166. } STACK;
  167.  
  168. static    RUN        *curr_run    = NULL;
  169. static    RUN        *first_run    = NULL;
  170. static    RUN        *last_run    = NULL;
  171. static    char    **line;
  172. static    FILE    *tfp            = NULL;
  173. static    HEAP        *heap;
  174. static    RUN        *run_pointer;
  175. static    HEAP        *heap_pointer;
  176. static    STACK        stack[STACKSIZE];
  177. static    STACK        *stackptr = &stack[STACKSIZE-1];
  178.  
  179. static    int    nline    =    0;
  180. static    int    nruns    =    0;
  181.  
  182. /*
  183.  * The following may be changed by the caller to modify the sort
  184.  */
  185.  
  186. extern    int    sort_l;        /* Maximum length            */
  187. extern    int    (*sort_c)();    /* Sort function            */
  188. extern    int    sort_r;        /* Reverse order            */
  189. extern    char    *sort_f;    /* Sort file name            */
  190.  
  191. extern    int    strcmp();    /* Default string compare        */
  192. int    sort_l    = 256;        /* Define maximum record length        */
  193. int    (*sort_c)() = &strcmp;    /* Define default compare routine    */
  194. int    sort_r    =    0;    /* Non-zero for reverse comparison    */
  195. char    *sort_f    =    TEMP;    /* Change for a different temp. file    */
  196. extern    long    ftell();    /* File position routine        */
  197.  
  198. static    int    first    =    1;
  199. static    int    lbuf    =    NULL;
  200. /*
  201.  * First values:
  202.  *    +1        Before first call of sorta (sorto illegal)
  203.  *     0        During calls to sorta
  204.  *    -1        During calls to sorto
  205.  */
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215. sorta(datum)
  216. char    *datum;
  217. /*
  218.  * Add datum to the stuff to be sorted
  219.  */
  220. {
  221.     register char    *cp;
  222.     register int    ndatum;
  223.     char        *malloc();
  224.     char        *nalloc();
  225.  
  226.     if (first != 0) {
  227.         /*
  228.          * First call of sorta().  Open the work file and the
  229.          * head of the linked list of run descriptors.
  230.          */
  231.         first = 0;
  232.         if ((tfp = fopen(sort_f, "wun")) == NULL) {
  233.             die("E-Cannot create temp file", sort_f);
  234.         }
  235.         /*
  236.          * This is necessary to allocate the work buffer
  237.          * before we run out of main memory.
  238.          */
  239.         putc(0, tfp);
  240.         line = nalloc(RUNSIZE * sizeof(char *));
  241.         curr_run  = nalloc(sizeof(RUN));
  242.         lbuf = nalloc(sort_l + 1);
  243.     }
  244.     if (datum != NULL) {
  245.         /*
  246.          * Add datum to the stuff to sort
  247.          */
  248.         ndatum = strlen(datum) + sizeof(char);
  249.         if (nline >= RUNSIZE || (cp = malloc(ndatum)) == NULL) {
  250.             /*
  251.              * Either the run is complete or we're out
  252.              * of dynamic memory.  Sort this run and
  253.              * save it, then allocate a new current run
  254.              * descriptor node.
  255.              */
  256.             quick(0, nline-1);
  257.             saverun();
  258.             curr_run = nalloc(sizeof(RUN));
  259.             cp  = nalloc(ndatum);
  260.         }
  261.         /*
  262.          * Save the datum.
  263.          */
  264.         strcpy(cp, datum);
  265.         line[nline++] = cp;
  266.     }
  267.     else {
  268.         /*
  269.          * sorta(NULL) called, finish off the last (partial) run
  270.          * and setup for sorto().  heap_pointer will be NULL
  271.          * if the data was so small it all fit in main memory.
  272.          */
  273.         quick(0, nline-1);
  274.         if (first_run == NULL) {
  275.             heap_pointer = NULL;
  276.             nruns = 0;
  277.         }
  278.         else {
  279.             /*
  280.              * Multiple runs, save the last, free up space,
  281.              * and get set for sorto().
  282.              */
  283.             saverun();
  284.             free(line);
  285. /*
  286.  *            if (freopen(sort_f, "run", tfp) == NULL)
  287.  */
  288.             fclose(tfp);
  289.             if ((tfp = fopen(sort_f, "run")) == NULL) {
  290.                 die("F-Can't reopen temp. file.", sort_f);
  291.             }
  292.             /*
  293.              * Get the dummy first byte to allocate the input
  294.              * buffer.
  295.              */
  296.             getc(tfp);
  297.             heap = nalloc(nruns * sizeof(HEAP));
  298.             run_pointer = first_run;
  299.             heap_pointer = heap;
  300.         }
  301.         first = -1;        /* Flag sorta(NULL) called    */
  302.     }
  303. }
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311. char *
  312. sorto(buffer)
  313. char    *buffer;    /* Where output goes                */
  314. /*
  315.  * Write the next record to the output buffer
  316.  */
  317. {
  318.     register RUN        *rp;
  319.     register HEAP        *hp;
  320.     register union {
  321.         char        *cp;
  322.         int        i;
  323.     } r;
  324.     char            *nalloc();
  325.     char            *getline();
  326.  
  327.     if (first != -1)
  328.         die("E-sorto out of sync", NULL);
  329.     if ((hp = heap_pointer) == NULL) {
  330.         /*
  331.          * Only one buffer load was given
  332.          */
  333.         if (nruns >= nline) {
  334.             goto alldone;
  335.         }
  336.         else {
  337.             strcpy(buffer, line[nruns]);
  338.             free(line[nruns]);
  339.             nruns++;
  340.             return(buffer);
  341.         }
  342.     }            
  343.     /*
  344.      * Multiple runs.
  345.      */
  346.     if ((rp = run_pointer) != NULL) {
  347.         /*
  348.          * First call of sorto().  Build the initial heap.
  349.          * This is done in two steps, following R. W. Floyd's
  350.          * method as given in N. Wirth:
  351.          * "Algorithms + Data Structures = Programs"
  352.          */
  353.         do {
  354.             hp->h_rp = rp;
  355.             if (((hp++)->h_lp = getline(rp)) == NULL) {
  356.                 die("F-Empty run.", sort_f);
  357.             }
  358.         } while ((rp = rp->r_rp) != NULL);
  359.         /*
  360.          * Now, sift the top half of the heap.
  361.          */
  362.         for (r.i = nruns/2; --r.i >= 0;)
  363.             sift(r.i);
  364.         run_pointer = NULL;        /* Do this once only    */
  365.     }
  366.     if (nruns) {
  367.         /*
  368.          * We have more data to do, get the smallest entry
  369.          * from the heap to the user's buffer, free the entry
  370.          * and refill the heap (sifting the new entry into
  371.          * place.
  372.          */
  373.         r.cp = heap[0].h_lp;
  374.         strcpy(buffer, r.cp);
  375.         free(r.cp);
  376.         if ((heap[0].h_lp = getline(heap[0].h_rp)) == NULL) {
  377.             --nruns;
  378.             heap[0].h_rp = heap[nruns].h_rp;
  379.             heap[0].h_lp = heap[nruns].h_lp;
  380.         }
  381.         sift(0);
  382.         return(buffer);
  383.     }
  384. alldone:
  385.     first = 1;            /* All done        */
  386.     free(lbuf);
  387.     if (tfp != NULL) {
  388.         fclose(tfp);
  389.         delete(TEMP);
  390.     }
  391.     return(NULL);
  392. }
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407. /*
  408.  * Quicksort as described in N. Wirths's
  409.  * "Algorithms + Data Structures = Programs"
  410.  * A pearl of software engineering.
  411.  *
  412.  */
  413.  
  414. quick()
  415.    {
  416.    register    i, j;
  417.    int        l, r;
  418.    char        *t;
  419.    char        *p;
  420.  
  421.    stackptr--;                          /* push initial partition on stack */
  422.    stackptr->lft = 0;
  423.    stackptr->rght = nline - 1;
  424.    do
  425.       {
  426.       l = stackptr->lft;                /* pop top partition from stack */
  427.       r = stackptr->rght;
  428.       stackptr++;
  429.       do
  430.          {
  431.          i = l;
  432.          j = r;
  433.          p = line[(l + r) / 2];       /* split partition */
  434.          do
  435.             {
  436.             while (compare(line[i], p) < 0) i++;
  437.             while (compare(p, line[j]) < 0) j--;
  438.             if (i <= j)
  439.                {
  440.                t = line[i];           /* swap position of recs */
  441.                line[i] = line[j];
  442.                line[j] = t;
  443.                i++;
  444.                j--;
  445.                }
  446.             } while (i <= j);
  447.          if (j-l < r-i)               /* continue sorting smaller section */
  448.             {
  449.             if (i < r)
  450.                {                       /* stack request for */
  451.                stackptr--;             /* sorting right partition */
  452.                if (stackptr < stack)
  453.                   error("Stack overflow.\n");
  454.                stackptr->lft = i;
  455.                stackptr->rght = r;
  456.                }
  457.             r = j;                     /* continue sorting left */
  458.             }
  459.          else
  460.             {
  461.             if (l < j)
  462.                {                       /* stack request for */
  463.                stackptr--;             /* sorting left partition */
  464.                if (stackptr < stack)
  465.                   error("Stack overflow.\n");
  466.                stackptr->lft = l;
  467.                stackptr->rght = j;
  468.                }
  469.             l = i;                     /* continue sorting right */
  470.             }
  471.          } while (l < r);
  472.       } while (stackptr != stack + STACKSIZE);
  473.    }
  474.  
  475.  
  476.  
  477.  
  478.  
  479. /*
  480.  * Sift an item through the heap. Handles variable size heap,
  481.  * sifting from node 'n' through the bottom (node 'nruns-1').
  482.  * Algorithm due to R.W. Floyd., described in Wirth (loc. cit.)
  483.  */
  484. sift(n)
  485. int n;                    /* Index of current top node */
  486.    {
  487.    register int        i, j;
  488.    register HEAP    *h;        /* Fast heap node pointer */
  489.    RUN            *trp;        /* Temp run ptr. */
  490.    char            *tlp;        /* Temp line ptr. */
  491.  
  492.    i = n;
  493.    h = heap;
  494.    trp = h[i].h_rp;
  495.    tlp = h[i].h_lp;
  496.  
  497.    while((j=2*i+1) < nruns)
  498.       {
  499.       if (j < nruns-1 && compare(h[j+1].h_lp, h[j].h_lp) < 0)
  500.          ++j;
  501.       if (compare(tlp, h[j].h_lp) <= 0)
  502.          break;
  503.       /*
  504.        * Sift.
  505.        */
  506.       h[i].h_rp = h[j].h_rp;
  507.       h[i].h_lp = h[j].h_lp;
  508.       i = j;
  509.       }
  510.    h[i].h_rp = trp;
  511.    h[i].h_lp = tlp;
  512.    }
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527. /*
  528.  * Get a line from the specified run
  529.  * on the temp. file.
  530.  * Pack the line into allocated storage
  531.  * and return a pointer to it.
  532.  * Return NULL if there are no lines left
  533.  * in the run; real end of file is an
  534.  * internal botch.
  535.  */
  536. static char *
  537. getline(rp)
  538. register RUN    *rp;
  539. {
  540.     register char    *cp;
  541.     register int    size;
  542.     char        *nalloc();
  543.  
  544.     if (rp->r_size == 0)
  545.         return (NULL);
  546.     fseek(tfp, rp->r_seek, 0);
  547.     size = fget(lbuf, sort_l, tfp);
  548.     if (feof(tfp)) {
  549.         fprintf(stderr, "run size = %d, seeked to %06o, read %d bytes",
  550.                 rp->r_size, rp->r_seek, size);
  551.         die("F-Unexpected end of file.", sort_f);
  552.     }
  553.     rp->r_seek = ftell(tfp);
  554.     --rp->r_size;
  555.     cp = nalloc(size);
  556.     strcpy(cp, lbuf);
  557.     return (cp);
  558. }
  559.  
  560.  
  561.  
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575. /*
  576.  * Save a run.
  577.  * The run block has been preallocated
  578.  * because there may not be enough space
  579.  * to allocate it now.
  580.  *
  581.  * Dump the lines in the array `line' to
  582.  * the temp. file.
  583.  */
  584. static
  585. saverun()
  586. {
  587.     register i;
  588.  
  589.     curr_run->r_rp = NULL;
  590.     curr_run->r_seek = ftell(tfp);
  591.     curr_run->r_size = nline;
  592.     if (first_run == NULL)
  593.         first_run = curr_run;
  594.     else
  595.         last_run->r_rp = curr_run;
  596.     last_run = curr_run;
  597.     ++nruns;
  598.     for (i=0; i<nline; ++i) {
  599.         fput(line[i], strlen(line[i]) + 1, tfp);
  600.         if (ferror(tfp)) {
  601.             die("E-error writing temp. file", sort_f);
  602.         }
  603.         free(line[i]);
  604.     }
  605.     nline = 0;
  606. }
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623. /*
  624.  * Compare routine.
  625.  */
  626. compare(a, b)
  627. char *a, *b;
  628. {
  629.     register c;
  630.  
  631.     c = (*sort_c)(a, b);
  632.     if (sort_r)
  633.         c = -c;
  634.     return (c);
  635. }
  636.  
  637. /*
  638.  * Allocate space.
  639.  * If no space, abort with a nasty
  640.  * little message.
  641.  */
  642. static char *
  643. nalloc(n)
  644. {
  645.     register char    *p;
  646.     char        *malloc();
  647.  
  648.     if ((p = malloc(n)) == NULL) {
  649.         die("E-out of main memory.", NULL);
  650.     }
  651.     return (p);
  652. }
  653.  
  654. static
  655. die(s, arg)
  656. char        *s;
  657. char        *arg;
  658. /*
  659.  * Abort routine
  660.  */
  661. {
  662.     if (arg != NULL)
  663.         perror(arg);
  664.     fprintf(stderr, "?SORTS-%s\n", s);
  665.     error("Cannot continue");
  666. }
  667.  
  668.